// 1. 游戏抽象类（需子类实现具体规则）
class Game {
  getCurrentPlayer() { throw Error("需实现getCurrentPlayer") }
  getLegalActions() { throw Error("需实现getLegalActions") }
  performAction(action) { throw Error("需实现performAction") }
  isTerminal() { throw Error("需实现isTerminal") }
  getResult() { throw Error("需实现getResult") }
}

// 2. 游戏实例类
/**
 *	 0	 1	 2	 3	 4	 5	 6
 *
 *	35	36	37	38	39	40	41
 *	28	29	30	31	32	33	34
 *	21	22	23	24	25	26	27
 *	14	15	16	17	18	19	20
 * 	 7	 8	 9	10	11	12	13
 *	 1	 2	 3	 4	 5	 6	 7
 *
 */
class Connect4 extends Game {
	constructor(width = 7, height = 6) {
		super();
		this.history = [];
		this.width = width;
		this.height = height;
		this.currentPlayer = 1;
		this.board = new Array(width * height).fill(0);
	}
	getCurrentPlayer() {
		return this.currentPlayer;
	}
	
	/**
	 * 返回可以落子的列号[0~6]，如果满盘则返回空数组
	 * @returns {array}
	 */
	getLegalActions() {
		let actions = [];
		for(let i = this.width * (this.height-1); i< this.board.length; i++){
			if(this.board[i] === 0){
				actions.push(i%this.width);
			}
		}
		return actions;
	}
	
	/**
	 * 执行一个动作
	 * @param {number} action 输入的动作，0~6
	 */
	 performAction(action) {
		let target = 0;
		for(let i = 0; i<this.height; i++){
			target = i * this.width + action;
			if(this.board[target] === 0){
				this.board[target] = this.currentPlayer;
				break;
			}
		}
		this.currentPlayer *= -1;
		this.history.push(target);
	 }
	 
	 /**
	  * 游戏是否结束
	  * @return {boolean} 游戏是否已经结束
	  */
	 isTerminal() {
		return !(this.getResult() === 0);
	 }
	 
	 /**
	  * 获取游戏赢家
	  * @return {number} 游戏赢家，1先手，-1后手， 1e-4平局，0尚未决出胜负
	  */
	 getResult(){
		//连四赢
		for(let range of WinRange.ranges){
			let dot = this.board.reduce((sum, val, i) => sum + val * range[i],0);
			if(Math.abs(dot) === 4){
				//console.log(range);
				return dot/4;
			}
		}
		//满盘平
		if(!this.board.some(val => val === 0 )){
			return 1e-4;
		}
		//无结果
		return 0;
	 }

	 clone(){
		let cloned = new Connect4(this.width, this.height);
		cloned.currentPlayer = this.currentPlayer;
		cloned.board = [...this.board];
		cloned.history = [...this.history];
		return cloned;
	 }
}

/**
 * 6行7列4子棋的69种赢法
 * @author hrwang
 * @version 1.0
 */
class WinRange {
	static ranges = [
		[
			0,0,0,1,0,0,0,
			0,0,1,0,0,0,0,
			0,1,0,0,0,0,0,
			1,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,1,0,0,0,
		],
		[
			0,0,0,1,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,1,
			0,0,0,0,0,1,0,
			0,0,0,0,1,0,0,
			0,0,0,1,0,0,0,
		],
		[
			0,0,0,0,1,0,0,
			0,0,0,1,0,0,0,
			0,0,1,0,0,0,0,
			0,1,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,1,0,0,0,0,
			0,1,0,0,0,0,0,
			1,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,1,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,1,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,1,
			0,0,0,0,0,1,0,
			0,0,0,0,1,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,1,0,
			0,0,0,0,1,0,0,
			0,0,0,1,0,0,0,
			0,0,1,0,0,0,0,
		],
		[
			1,0,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,0,1,0,
		],
		[
			0,0,0,0,0,0,1,
			0,0,0,0,0,1,0,
			0,0,0,0,1,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,1,0,
			0,0,0,0,1,0,0,
			0,0,0,1,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,1,0,0,0,
			0,0,1,0,0,0,0,
			0,1,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,0,1,
		],
		[
			0,0,0,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,0,0,
		],
		[
			0,1,0,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,1,0,0,0,0,
			0,1,0,0,0,0,0,
			1,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,1,0,0,0,
			0,0,1,0,0,0,0,
			0,1,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,1,0,
			0,0,0,0,1,0,0,
			0,0,0,1,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			1,1,1,1,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,1,1,1,1,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,1,1,1,1,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,1,1,1,1,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			1,1,1,1,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,1,1,1,1,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,1,1,1,1,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,1,1,1,1,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			1,1,1,1,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,1,1,1,1,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,1,1,1,1,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,1,1,1,1,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			1,1,1,1,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,1,1,1,1,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,1,1,1,1,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,1,1,1,1,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			1,1,1,1,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,1,1,1,1,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,1,1,1,1,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,1,1,1,1,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			1,1,1,1,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,1,1,1,1,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,1,1,1,1,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,1,1,1,1,
		],
		[
			1,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
			1,0,0,0,0,0,0,
		],
		[
			0,1,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,1,0,0,0,0,0,
			0,1,0,0,0,0,0,
		],
		[
			0,0,1,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,1,0,0,0,0,
			0,0,1,0,0,0,0,
		],
		[
			0,0,0,1,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,1,0,0,0,
			0,0,0,1,0,0,0,
		],
		[
			0,0,0,0,1,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,1,0,0,
			0,0,0,0,1,0,0,
		],
		[
			0,0,0,0,0,1,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,1,0,
			0,0,0,0,0,1,0,
		],
		[
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,0,
		],
		[
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,0,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,1,
			0,0,0,0,0,0,1,
		],
	];
}